package com.yanceysong.codetop.s11_s20;

/**
 * @ClassName S13_Mid_33_搜索旋转排序数组
 * @Description
 * @date 2025/8/17 22:22
 * @Author yanceysong
 * @Version 1.0
 */
public class S13_Mid_33_搜索旋转排序数组 {
    /**
     * LeetCode：
     * <a href="https://leetcode.cn/problems/search-in-rotated-sorted-array/description/">...</a>
     * <p>
     * 整数数组 nums 按升序排列，数组中的值 互不相同 。
     * <p>
     * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
     * 使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
     * 例如， [0,1,2,4,5,6,7] 下标3上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
     * <p>
     * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
     * <p>
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [4,5,6,7,0,1,2], target = 0
     * 输出：4
     * 示例 2：
     * <p>
     * 输入：nums = [4,5,6,7,0,1,2], target = 3
     * 输出：-1
     * 示例 3：
     * <p>
     * 输入：nums = [1], target = 0
     * 输出：-1
     * <p>
     * <p>
     * 提示：
     * <p>
     * 1 <= nums.length <= 5000
     * -104 <= nums[i] <= 104
     * nums 中的每个值都 独一无二
     * 题目数据保证 nums 在预先未知的某个下标上进行了旋转
     * -104 <= target <= 104
     * <p>
     * ==================== 搜索旋转排序数组算法图解 ====================
     * <p>
     * 算法思路：两次二分查找
     * 1. 第一次二分：找到旋转点（分割点）
     * 2. 第二次二分：在正确的有序区间内查找目标值
     * <p>
     * 旋转数组特点分析：
     * 原数组: [0, 1, 2, 4, 5, 6, 7]
     * 旋转后: [4, 5, 6, 7, 0, 1, 2]  (在索引3处旋转)
     * .       ↑-------↑  ↑-------↑
     * 左半部分   右半部分
     * (有序)     (有序)
     * <p>
     * 关键观察：
     * - 旋转数组由两个有序部分组成
     * - 左半部分的所有元素 >= nums[0]
     * - 右半部分的所有元素 < nums[0]
     * - 旋转点是左半部分的最后一个元素
     * <p>
     * 执行示例：nums = [4,5,6,7,0,1,2], target = 0
     * <p>
     * 第一阶段：找旋转点
     * 数组: [4, 5, 6, 7, 0, 1, 2]
     * .     0  1  2  3  4  5  6  (索引)
     * <p>
     * 目标：找到满足 nums[i] >= nums[0] 的最大索引i
     * nums[0] = 4，寻找 >= 4 的最大索引
     * <p>
     * 第1轮二分：left=0, right=6
     * mid = (0 + 6 + 1) / 2 = 3
     * nums[3] = 7 >= nums[0] = 4 ✓
     * 更新：left = 3
     * <p>
     * 第2轮二分：left=3, right=6
     * mid = (3 + 6 + 1) / 2 = 5
     * nums[5] = 1 < nums[0] = 4 ✗
     * 更新：right = 4
     * <p>
     * 第3轮二分：left=3, right=4
     * mid = (3 + 4 + 1) / 2 = 4
     * nums[4] = 0 < nums[0] = 4 ✗
     * 更新：right = 3
     * <p>
     * 结束：left = right = 3，旋转点索引为3
     * <p>
     * 数组分析：
     * [4, 5, 6, 7, 0, 1, 2]
     * ,↑-------↑  ↑-------↑
     * 左半部分    右半部分
     * [0,3]      [4,6]
     * <p>
     * 第二阶段：确定搜索区间
     * target = 0, nums[0] = 4
     * target < nums[0] → target在右半部分
     * 搜索区间：[4, 6]
     * <p>
     * 第三阶段：在有序区间内二分查找
     * 在区间 [4, 6] 中查找 target = 0
     * <p>
     * 第1轮二分：left=4, right=6
     * mid = (4 + 6) / 2 = 5
     * nums[5] = 1 >= target = 0 ✓
     * 更新：right = 5
     * <p>
     * 第2轮二分：left=4, right=5
     * mid = (4 + 5) / 2 = 4
     * nums[4] = 0 >= target = 0 ✓
     * 更新：right = 4
     * <p>
     * 结束：left = right = 4
     * 验证：nums[4] = 0 == target ✓
     * 返回：4
     * <p>
     * 算法分析：
     * 时间复杂度：O(log n) - 两次二分查找
     * 空间复杂度：O(1) - 只使用常数额外空间
     * <p>
     * 关键技巧：
     * 1. 利用 nums[0] 作为分界点判断元素位置
     * 2. 第一次二分使用 (left + right + 1) / 2 避免死循环
     * 3. 第二次二分使用标准二分查找模板
     * <p>
     * 边界情况处理：
     * - 数组长度为0：直接返回-1
     * - 数组长度为1：直接比较
     * - 未旋转数组：算法仍然正确工作
     * - target不存在：最终验证阶段返回-1
     * <p>
     * 两种搜索区间的选择：
     * if (target >= nums[0]):
     * 搜索左半部分 [0, rotationPoint]
     * else:
     * 搜索右半部分 [rotationPoint+1, n-1]
     * <p>
     * ================================================================
     */
    public int search(int[] nums, int target) {
        int arrayLength = nums.length;

        // 边界情况处理
        if (arrayLength == 0) return -1;
        if (arrayLength == 1) return nums[0] == target ? 0 : -1;

        // 第一阶段：二分查找旋转点
        // 目标：找到满足 nums[i] >= nums[0] 的最大索引i
        int rotationSearchLeft = 0;
        int rotationSearchRight = arrayLength - 1;
        int firstElement = nums[0];  // 用作分界点的第一个元素

        while (rotationSearchLeft < rotationSearchRight) {
            // 使用 (left + right + 1) / 2 避免死循环
            int rotationSearchMid = (rotationSearchLeft + rotationSearchRight + 1) >> 1;

            if (nums[rotationSearchMid] >= firstElement) {
                // mid在左半部分，旋转点在mid或mid右边
                rotationSearchLeft = rotationSearchMid;
            } else {
                // mid在右半部分，旋转点在mid左边
                rotationSearchRight = rotationSearchMid - 1;
            }
        }

        int rotationPointIndex = rotationSearchLeft;  // 旋转点索引

        // 第二阶段：确定目标值所在的有序区间
        int targetSearchLeft;   // 目标搜索的左边界
        int targetSearchRight;  // 目标搜索的右边界

        if (target >= firstElement) {
            // target在左半部分（较大值区间）：[0, rotationPointIndex]
            targetSearchLeft = 0;
            targetSearchRight = rotationPointIndex;
        } else {
            // target在右半部分（较小值区间）：[rotationPointIndex+1, arrayLength-1]
            targetSearchLeft = rotationPointIndex + 1;
            targetSearchRight = arrayLength - 1;
        }

        // 第三阶段：在确定的有序区间内进行标准二分查找
        while (targetSearchLeft < targetSearchRight) {
            int targetSearchMid = (targetSearchLeft + targetSearchRight) >> 1;

            if (nums[targetSearchMid] >= target) {
                // mid位置的值大于等于target，答案在左半边
                targetSearchRight = targetSearchMid;
            } else {
                // mid位置的值小于target，答案在右半边
                targetSearchLeft = targetSearchMid + 1;
            }
        }

        // 验证找到的位置是否为目标值
        int candidateIndex = targetSearchRight;
        return nums[candidateIndex] == target ? candidateIndex : -1;
    }

    public static void main(String[] args) {
        S13_Mid_33_搜索旋转排序数组 solution = new S13_Mid_33_搜索旋转排序数组();

        System.out.println("=== 搜索旋转排序数组测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同旋转点测试
        System.out.println("\n--- 测试3: 不同旋转点测试 ---");
        testDifferentRotations(solution);

        // 测试4: 特殊情况测试
        System.out.println("\n--- 测试4: 特殊情况测试 ---");
        testSpecialCases(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 打印数组的辅助方法
     */
    private static void printArray(int[] arr) {
        if (arr.length == 0) {
            System.out.print("[]");
            return;
        }

        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(",");
            }
        }
        System.out.print("]");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S13_Mid_33_搜索旋转排序数组 solution) {
        // 示例1: nums = [4,5,6,7,0,1,2], target = 0 -> 4
        int[] nums1 = {4, 5, 6, 7, 0, 1, 2};
        int target1 = 0;
        int expected1 = 4;

        int result1 = solution.search(nums1, target1);

        System.out.print("输入: ");
        printArray(nums1);
        System.out.println(", target=" + target1 + " -> 输出: " + result1 + " (期望: " + expected1 + ")");

        assert result1 == expected1 : "示例1测试失败";

        // 示例2: nums = [4,5,6,7,0,1,2], target = 3 -> -1
        int[] nums2 = {4, 5, 6, 7, 0, 1, 2};
        int target2 = 3;
        int expected2 = -1;

        int result2 = solution.search(nums2, target2);

        System.out.print("输入: ");
        printArray(nums2);
        System.out.println(", target=" + target2 + " -> 输出: " + result2 + " (期望: " + expected2 + ")");

        assert result2 == expected2 : "示例2测试失败";

        // 示例3: nums = [1], target = 0 -> -1
        int[] nums3 = {1};
        int target3 = 0;
        int expected3 = -1;

        int result3 = solution.search(nums3, target3);

        System.out.print("输入: ");
        printArray(nums3);
        System.out.println(", target=" + target3 + " -> 输出: " + result3 + " (期望: " + expected3 + ")");

        assert result3 == expected3 : "示例3测试失败";

        // 补充示例: 找到左半部分的元素
        int[] nums4 = {4, 5, 6, 7, 0, 1, 2};
        int target4 = 6;
        int expected4 = 2;

        int result4 = solution.search(nums4, target4);

        System.out.print("输入: ");
        printArray(nums4);
        System.out.println(", target=" + target4 + " -> 输出: " + result4 + " (期望: " + expected4 + ")");

        assert result4 == expected4 : "补充示例测试失败";

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S13_Mid_33_搜索旋转排序数组 solution) {
        // 测试1: 单个元素，找到
        int[] nums1 = {5};
        int target1 = 5;
        int expected1 = 0;

        int result1 = solution.search(nums1, target1);

        System.out.print("单个元素找到: ");
        printArray(nums1);
        System.out.println(", target=" + target1 + " -> 输出: " + result1 + " (期望: " + expected1 + ")");

        assert result1 == expected1 : "单个元素找到测试失败";

        // 测试2: 单个元素，未找到
        int[] nums2 = {5};
        int target2 = 3;
        int expected2 = -1;

        int result2 = solution.search(nums2, target2);

        System.out.print("单个元素未找到: ");
        printArray(nums2);
        System.out.println(", target=" + target2 + " -> 输出: " + result2 + " (期望: " + expected2 + ")");

        assert result2 == expected2 : "单个元素未找到测试失败";

        // 测试3: 两个元素
        int[] nums3 = {3, 1};
        int target3 = 1;
        int expected3 = 1;

        int result3 = solution.search(nums3, target3);

        System.out.print("两个元素: ");
        printArray(nums3);
        System.out.println(", target=" + target3 + " -> 输出: " + result3 + " (期望: " + expected3 + ")");

        assert result3 == expected3 : "两个元素测试失败";

        // 测试4: 未旋转的数组（旋转点在末尾）
        int[] nums4 = {1, 2, 3, 4, 5};
        int target4 = 3;
        int expected4 = 2;

        int result4 = solution.search(nums4, target4);

        System.out.print("未旋转数组: ");
        printArray(nums4);
        System.out.println(", target=" + target4 + " -> 输出: " + result4 + " (期望: " + expected4 + ")");

        assert result4 == expected4 : "未旋转数组测试失败";

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同旋转点
     */
    private static void testDifferentRotations(S13_Mid_33_搜索旋转排序数组 solution) {
        int[] original = {0, 1, 2, 4, 5, 6, 7};  // 原始有序数组

        // 测试不同的旋转位置
        for (int rotatePos = 0; rotatePos < original.length; rotatePos++) {
            // 创建旋转数组
            int[] rotated = new int[original.length];
            for (int i = 0; i < original.length; i++) {
                rotated[i] = original[(i + rotatePos) % original.length];
            }

            // 测试查找每个元素
            for (int target : original) {
                int result = solution.search(rotated, target);
                int expected = -1;

                // 找到target在旋转数组中的正确位置
                for (int i = 0; i < rotated.length; i++) {
                    if (rotated[i] == target) {
                        expected = i;
                        break;
                    }
                }

                System.out.print("旋转" + rotatePos + "位: ");
                printArray(rotated);
                System.out.println(", target=" + target + " -> 输出: " + result + " (期望: " + expected + ")");

                assert result == expected : "旋转位置" + rotatePos + "，目标" + target + "测试失败";
            }
        }

        System.out.println("✓ 不同旋转点测试通过");
    }

    /**
     * 测试特殊情况
     */
    private static void testSpecialCases(S13_Mid_33_搜索旋转排序数组 solution) {
        // 测试1: 包含负数
        int[] nums1 = {-2, -1, 0, 3, 4, 5, -5, -4, -3};  // 在索引6处旋转
        testSearchCase(solution, nums1, 0, 2, "包含负数-找到");
        testSearchCase(solution, nums1, -3, 8, "包含负数-找到末尾");
        testSearchCase(solution, nums1, 10, -1, "包含负数-未找到");

        // 测试2: 大数值
        int[] nums2 = {1000, 2000, 3000, 100, 200, 300};
        testSearchCase(solution, nums2, 2000, 1, "大数值-找到");
        testSearchCase(solution, nums2, 200, 4, "大数值-找到");
        testSearchCase(solution, nums2, 1500, -1, "大数值-未找到");

        // 测试3: 最小和最大值
        int[] nums3 = {3, 4, 5, 1, 2};
        testSearchCase(solution, nums3, 1, 3, "最小值");
        testSearchCase(solution, nums3, 5, 2, "最大值");

        // 测试4: 旋转点在开头（实际未旋转）
        int[] nums4 = {1, 2, 3, 4, 5, 6, 7};
        testSearchCase(solution, nums4, 4, 3, "未旋转数组");
        testSearchCase(solution, nums4, 8, -1, "未旋转数组-未找到");

        // 测试5: 旋转点在末尾
        int[] nums5 = {2, 3, 4, 5, 6, 7, 1};
        testSearchCase(solution, nums5, 1, 6, "旋转点在末尾");
        testSearchCase(solution, nums5, 5, 3, "旋转点在末尾-找到");

        System.out.println("✓ 特殊情况测试通过");
    }

    /**
     * 辅助方法：测试搜索情况
     */
    private static void testSearchCase(S13_Mid_33_搜索旋转排序数组 solution, int[] nums, int target, int expected, String description) {
        int result = solution.search(nums, target);

        System.out.print(description + " - ");
        printArray(nums);
        System.out.println(", target=" + target + " -> 输出: " + result + " (期望: " + expected + ")");

        assert result == expected : description + "测试失败";
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S13_Mid_33_搜索旋转排序数组 solution) {
        // 测试1: 中等规模
        System.out.println("性能测试1: 1000个元素");
        testPerformanceCase(solution, 1000);

        // 测试2: 较大规模
        System.out.println("性能测试2: 5000个元素");
        testPerformanceCase(solution, 5000);

        // 测试3: 最坏情况 - 目标不存在
        System.out.println("性能测试3: 最坏情况 - 目标不存在");
        testWorstCase(solution);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S13_Mid_33_搜索旋转排序数组 solution, int size) {
        // 创建有序数组
        int[] original = new int[size];
        for (int i = 0; i < size; i++) {
            original[i] = i * 2;  // 0, 2, 4, 6, ...
        }

        // 在中间位置旋转
        int rotatePos = size / 3;
        int[] rotated = new int[size];
        for (int i = 0; i < size; i++) {
            rotated[i] = original[(i + rotatePos) % size];
        }

        // 测试查找中间元素
        int target = original[size / 2];

        long startTime = System.currentTimeMillis();
        int result = solution.search(rotated, target);
        long endTime = System.currentTimeMillis();

        // 验证结果正确性
        assert result != -1 : "性能测试：应该找到目标元素";
        assert rotated[result] == target : "性能测试：找到的位置不正确";

        System.out.println("  数组大小: " + size + ", target=" + target +
                           ", 结果索引: " + result +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        // 验证时间复杂度为O(log n)
        assert (endTime - startTime) < 100 : "性能测试：执行时间过长，可能存在性能问题";
    }

    /**
     * 辅助方法：最坏情况性能测试
     */
    private static void testWorstCase(S13_Mid_33_搜索旋转排序数组 solution) {
        // 创建大数组，查找不存在的元素
        int size = 5000;
        int[] nums = new int[size];
        for (int i = 0; i < size; i++) {
            nums[i] = i * 2 + 1;  // 1, 3, 5, 7, ... (奇数)
        }

        // 在1/4处旋转
        int rotatePos = size / 4;
        int[] rotated = new int[size];
        for (int i = 0; i < size; i++) {
            rotated[i] = nums[(i + rotatePos) % size];
        }

        // 查找不存在的偶数
        int target = 1000;  // 偶数，不在奇数数组中

        long startTime = System.currentTimeMillis();
        int result = solution.search(rotated, target);
        long endTime = System.currentTimeMillis();

        // 验证结果
        assert result == -1 : "最坏情况：应该返回-1";

        System.out.println("  最坏情况测试 - 数组大小: " + size + ", target=" + target +
                           ", 结果: " + result +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        assert (endTime - startTime) < 50 : "最坏情况：执行时间过长";
    }

}
